package com.janko.springbootbase.algorithm;

/**
 * @Author nyk
 * @Date 2021/3/16 12:09
 * @Version 1.0
 * @Desc 二分查找 ：比较次数少，查找速度快，平均性能好
 * 缺点：待查表为有序表，且插入删除困难
 */
public class BinarySearch {
    private static volatile BinarySearch binarySearch;

    public BinarySearch() {
    }

    public static BinarySearch getSingleton() {
        if (null == binarySearch) {
            synchronized (BinarySearch.class) {
                if (null == binarySearch) {
                    binarySearch = new BinarySearch();
                }
            }
        }
        return binarySearch;
    }


    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5, 6, 7, 22, 23, 25, 64};
        int index = recursionSearch(arr, 7, 0, arr.length - 1);
        System.out.println(arr[index]);

        System.out.println(arr[getWhileSearch(arr, 7)]);
    }


    public static int getWhileSearch(int[] arr, int key) {
        int low = 0;
        int high = arr.length - 1;
        int middle = 0;            //定义middle

        if (key < arr[low] || key > arr[high] || low > high) {
            return -1;
        }
        while (high >= low) {
            middle = (low + high) / 2;
            if (arr[middle] > key) {
                high = middle - 1;
            } else if (arr[middle] < key) {
                low = middle + 1;
            } else {
                return middle;
            }
        }
        return -1;
    }

    /**
     * 递归查询目标key位置
     *
     * @param arr  被查找的数据
     * @param key  查询的key值
     * @param low  最开始的数组大小
     * @param high 最大的数据大小值
     * @return 目标key所在的位置
     */
    public static int recursionSearch(int[] arr, int key, int low, int high) {
        if (key < arr[low] || key > arr[high] || low > high) {
            return -1;
        }
        int mid = (low + high) / 2;
        if (arr[mid] > key) {
            System.out.println("arr[mid]=:  " + arr[mid]);
            // 比key大  说明key在左边 那么函数的high就应该调整为mid-1
            return recursionSearch(arr, key, low, mid - 1);
        } else if (arr[mid] < key) {
            System.out.println("arr[mid]=:  " + arr[mid]);
            // 中间值比key小  key在右边
            return recursionSearch(arr, key, mid + 1, high);
        } else {
            return mid;
        }
    }
}
